P2365 & P5785 任务安排

两道题的转移式是一样的,只是优化不同。

dp(i)dp(i) 为完成前 ii 个任务的最小花费。

你会发现每次操作后总时间会增加 ss ,这样就不好处理当前时间。

所以可以用前几周讲到的方法,将 ss 的贡献提前计算,那么有转移

dp(i)=min{dp(j)+(SumciSumcj)(Sumti+s)+s(SumcnSumci)}   (0j<i)dp(i)=\min\{dp(j)+(Sumc_i-Sumc_j)(Sumt_i+s)+s(Sumc_n-Sumc_i)\} ~~~ (0 \le j <i)

dp(i)=min{dp(j)+(SumciSumcj)Sumti+s(SumcnSumcj)}   (0j<i)dp(i)=\min\{dp(j)+(Sumc_i-Sumc_j)Sumt_i+s(Sumc_n-Sumc_j)\} ~~~ (0 \le j <i)

将与 jj 无关的提到外面来

dp(i)=min{dp(j)SumcjSumtisSumcj}+SumciSumti+sSumcn   (0j<i)dp(i)=\min\{dp(j)-Sumc_jSumt_i-sSumc_j\}+Sumc_iSumt_i+sSumc_n ~~~ (0 \le j <i)

我们只需要求出 dp(j)SumcjSumtisSumcjdp(j)-Sumc_jSumt_i-sSumc_j 的最小值即可。

P2365

假设有两个决策点 j<kj<k ,且 jjkk 优。

那么有:

dp(j)SumcjSumtisSumcj<dp(k)SumckSumtisSumckdp(j)-Sumc_jSumt_i-sSumc_j<dp(k)-Sumc_kSumt_i-sSumc_k

(dp(j)sSumcj)(dp(k)sSumck)<Sumti(SumcjSumck)(dp(j)-sSumc_j)-(dp(k)-sSumc_k)<Sumt_i(Sumc_j-Sumc_k)

(dp(j)sSumcj)(dp(k)sSumck)(SumcjSumck)>Sumti\frac{(dp(j)-sSumc_j)-(dp(k)-sSumc_k)}{(Sumc_j-Sumc_k)}>Sumt_i

这里变号是因为 SumcjSumck<0Sumc_j-Sumc_k<0

然后就可以斜率优化了。

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
#define LL long long

const int MAXN = 3e5;
int n , s , T[ MAXN + 5 ] , C[ MAXN + 5 ];
int Que[ MAXN + 5 ] , Head , Tail;
LL dp[ MAXN + 5 ];

LL fx( int i ) { return C[ i ]; }
LL fy( int i ) { return dp[ i ] - s * C[ i ]; }
double Slope( int i , int j ) {
	return ( fy( i ) - fy( j ) ) * 1.0 / ( fx( i ) - fx( j ) );
}

int main( ) {
	scanf("%d %d",&n,&s);
	for( int i = 1 ; i <= n ; i ++ ) {
		scanf("%d %d",&T[ i ],&C[ i ]);
		T[ i ] += T[ i - 1 ] , C[ i ] += C[ i - 1 ];
	}
	
	Head = 1 , Tail = 0; Que[ ++ Tail ] = 0;
	for( int i = 1 ; i <= n ; i ++ ) {
		for( ; Head + 1 <= Tail && Slope( Que[ Head ] , Que[ Head + 1 ] ) <= T[ i ] ; Head ++ );
		dp[ i ] = dp[ Que[ Head ] ] + 1ll * ( C[ i ] - C[ Que[ Head ] ] ) * T[ i ] + s * ( C[ n ] - C[ Que[ Head ] ] );
		for( ; Head + 1 <= Tail && Slope( Que[ Tail - 1 ] , Que[ Tail ] ) > Slope( Que[ Tail ] , i ) ; Tail -- );
		Que[ ++ Tail ] = i;	
	}
	printf("%lld\n", dp[ n ] );
	return 0;
}

P5785

这道题看起来和上一道一样,但是 tt 可以为负数。

这就意味着 SumtSumt 不一定递增,不能直接删掉斜率不大于 SumtSumt 的点。

但是仍然可以维护一个斜率递增的队列,在里面二分就可以了。

这道题卡精度,不要用除法。

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
#define LL long long

const int MAXN = 3e5;
int n , s , T[ MAXN + 5 ] , C[ MAXN + 5 ];
int Que[ MAXN + 5 ] , Head , Tail;
LL dp[ MAXN + 5 ];

LL fx( int i ) { return C[ i ]; }
LL fy( int i ) { return dp[ i ] - 1ll * s * C[ i ]; }

signed main( ) {
	scanf("%d %d",&n,&s);
	for( int i = 1 ; i <= n ; i ++ ) {
		scanf("%d %d",&T[ i ],&C[ i ]);
		T[ i ] += T[ i - 1 ] , C[ i ] += C[ i - 1 ];
	}
	
	Head = 1 , Tail = 0; Que[ ++ Tail ] = 0;
	for( int i = 1 , opt = 0 ; i <= n ; i ++ ) {
		for( int l = Head , r = Tail ; l <= r ;  ) {
			int Mid = ( l + r ) >> 1;
			if( Mid != Tail && ( fy( Que[ Mid ] ) - fy( Que[ Mid + 1 ] ) ) >= T[ i ] * ( fx( Que[ Mid ] ) - fx( Que[ Mid + 1 ] ) ) ) l = Mid + 1;
			else r = Mid - 1 , opt = Que[ Mid ];
		}
		dp[ i ] = dp[ opt ] + 1ll * ( C[ i ] - C[ opt ] ) * T[ i ] + 1ll * s * ( C[ n ] - C[ opt ] );
		for( ; Head + 1 <= Tail && ( fy( Que[ Tail - 1 ] ) - fy( Que[ Tail ] ) ) * ( fx( Que[ Tail ] ) - fx( i ) ) >= ( ( fy( Que[ Tail ] ) - fy( i ) )  ) * ( fx( Que[ Tail - 1 ] ) - fx( Que[ Tail ] ) ) ; Tail -- );
		Que[ ++ Tail ] = i;
	}
	printf("%lld\n", dp[ n ] );
	return 0;
}